class Solution {
public:
    void getNext(vector<int>& next,string& s){
        int j = 0;
        for(int i = 1;i < s.size();i++){
            while(j > 0 && s[j] != s[i]){
                j = next[j - 1];
            }
            if(s[j] == s[i]){
                j++;
            }
            next[i] = j;
        }
    }
    int strStr(string& a,string& b){
        vector<int> next(b.size(),0);
        getNext(next,b);
        
        for(int i = 0,j = 0;i - j < a.size();i++){
            while(j > 0 && a[i % a.size()] != b[j]){
                j = next[j - 1];
            }
            
            if(a[i % a.size()] == b[j]){
                j++;
            }
            if(j == b.size()){
                return i;
            }
        }
        return -1;
    }
    int repeatedStringMatch(string a, string b) {
        int ans = strStr(a,b);
        if(ans == -1) return -1;
        if(ans < a.size()){
            return 1;
        }
        return (ans - a.size() ) / a.size() + 2;
    }
};
